package sort;

/**
 * 插入排序算法，排序流程如下:
 * (1)首先对数组的前两个数据进行从小到大的排序。
 * (2)接着将第3个数据与排好序的两个数据比较，将第3个数据插入到合适的位置
 * (3)然后，将第4个数据插入到已排好序的前3个数据中。
 * (4)不断重复上述过程，直到把最后一个数据插入合适的位置。最后便完成了对原始数据从小到大的排序。
 */

public class InsertSort {
    public static void main(String[] args){
     insertionSort(new int[]{5,4,3,2,1});
    }
    public static void insertionSort(int[] array){
        int temp;
        int beforeIndex;
        for(int currentIndex=1;currentIndex<array.length;currentIndex++){
             temp=array[currentIndex];
             beforeIndex=currentIndex-1;
            //如果已经遍历过第一个数据或者前面某个数据大于了本轮下标对应的数据
            // 就开始将签名的数据向后移动,如果前面的数据还大继续前面的数据继续向后移动
            //直到前面的数据更小或者是到了第一个位置就结束循环
             while(beforeIndex>=0&&temp<array[beforeIndex]){
                 array[beforeIndex+1]=array[beforeIndex];
                 beforeIndex--;
             }
             //把找到的位置赋值为本轮数据，因为找到的位置后面的数据都已经向后移动了
            //所以可以直接给找到的位置放数据
             array[beforeIndex+1]=temp;
            System.out.println("第"+currentIndex+"步排序结果");
            for(int h=0;h<array.length;h++){
                System.out.println(" "+array[h]);
            }
            System.out.println("\n");
         }
    }
}
